package com.sicheng.lc.周赛.分类.线段树;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/21 22:53
 */
public class 花期内花的数目 {
    class Tree {
        int ls;
        int rs;
        int lazy;
        int sum;
    }

    int cnt = 1;
    int N = (int) 1e6;
    int M = (int) 1e9;
    Tree[] tree = new Tree[N];

    void lazyCreate(int st) {
        if (tree[st] == null) {
            tree[st] = new Tree();
        }

        if (tree[st].ls == 0) {
            cnt++;
            tree[st].ls = cnt;
            tree[cnt] = new Tree();
        }
        if (tree[st].rs == 0) {
            cnt++;
            tree[st].rs = cnt;
            tree[cnt] = new Tree();
        }
    }

    void pushUp(int st) {
        tree[st].sum = tree[tree[st].ls].sum + tree[tree[st].rs].sum;
    }

    void pushDown(int st, int l) {
        if (tree[st].lazy > 0) {
            tree[tree[st].ls].lazy += tree[st].lazy;
            tree[tree[st].rs].lazy += tree[st].lazy;
            tree[tree[st].ls].sum += tree[st].lazy * (l - (l >> 1));
            tree[tree[st].rs].sum += tree[st].lazy * (l >> 1);
            tree[st].lazy = 0;
        }
    }

    void add(int l, int r) {
        add(l, r, 1, 1, M);
    }

    void add(int l, int r, int st, int ll, int rr) {
        lazyCreate(st);
        if (l == ll && r == rr) {
            tree[st].lazy += 1;
            tree[st].sum += (r - l + 1);
            return;
        }

        pushDown(st, rr - ll + 1);
        int mid = rr + ll >> 1;
        if (r <= mid) {
            add(l, r, tree[st].ls, ll, mid);
        } else if (l > mid) {
            add(l, r, tree[st].rs, mid + 1, rr);
        } else {
            add(l, mid, tree[st].ls, ll, mid);
            add(mid + 1, r, tree[st].rs, mid + 1, rr);
        }
        pushUp(st);

    }

    int query(int l, int r) {
        return query(l, r, 1, 1, M);
    }

    int query(int l, int r, int st, int ll, int rr) {

        lazyCreate(st);
        if (l == ll && r == rr) {
            return tree[st].sum;
        }

        pushDown(st, rr - ll + 1);
        int mid = ll + ((rr - ll) >> 1);
        int res = 0;
        if (r <= mid) {
            res = query(l, r, tree[st].ls, ll, mid);
        } else if (l > mid) {
            res = query(l, r, tree[st].rs, mid + 1, rr);
        } else {
            res += query(l, mid, tree[st].ls, ll, mid);
            res += query(mid + 1, r, tree[st].rs, mid + 1, rr);
        }
        return res;

    }

    public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
        for (int[] flower : flowers) {
            add(flower[0], flower[1]);
        }
        for (int i = 0; i < persons.length; i++) {
            persons[i] = query(persons[i], persons[i]);
        }
        return persons;
    }

    public static void main(String[] args) {
        花期内花的数目 solution = new 花期内花的数目();


        int[][] flowers = {{21, 34}, {17, 37}, {23, 43}, {17, 46}, {37, 41}, {44, 45}, {32, 45}};
        int[] persons = {31, 41, 10, 12};
        int[] res = solution.fullBloomFlowers(flowers, persons);
        System.out.println(Arrays.toString(res));
    }
}
